#
# @lc app=leetcode.cn id=433 lang=python3
#
# [433] 最小基因变化
#

# @lc code=start
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        if start == end:
            return 0

        bankSet: Set[str] = set(bank)

        if end not in bankSet:
            return -1

        keys = ['A', 'C', 'G', 'T']
        visited: Set[str] = set()
        que: list[dict(str, int)] = [{'dna': start, 'step': 0}]
        visited.add(start)

        while (len(que)):
            curr = que.pop(0)
            dna = curr['dna']
            step = curr['step']

            if dna == end:
                return step

            for i in range(len(dna)):
                for k in range(len(keys)):
                    if (dna[i] == keys[k]):
                        continue
                    next = dna[:i] + keys[k] + dna[i + 1:]
                    if (next in visited or next not in bankSet):
                        continue
                    que.append({'dna': next, 'step': step + 1})
                    visited.add(next)
        return -1
# @lc code=end
